package com.example.demo.tixiban;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author xujm
 * @version V2.4
 *
 *  给一堆线段，求重合线段数最多的点，重合的线段数是几个?
 *
 *  思路二: 根据小根堆求解,
 *  把线段从小到大排序
 *  遍历:
 *      把当前线段尾部放到小根堆里面，(认为是一个重合的部分)
 *      将小根堆中 小于等于线段头部的值 全部弹出(弹出就是去除不重合的线段)
 *      小根堆中现在存在的值 的数量，即是现在有几条线段重合了
 * @since 2.4.0 2022/3/12 11:34
 */
public class Arr_求最大重合的线段数 {

    public static int duplicty(int [][] arr){

        int count = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });

        for(int i = 0;i<arr.length;i++){
            int[] temp = arr[i];
            queue.add(temp[1]);
            while(queue.peek() <= temp[0]){
                queue.poll();
            }
            count = Math.max(count,queue.size());
        }
        return count;
    }



    public static void main(String[] args) {

        int [][] arr = {{1,5},{2,6},{3,7},{6,7}};
        System.out.println(duplicty(arr));
    }

}
